# 0-1背包问题：重量W，物品数量N，价值数组v，重量数组w      求背包能装的最大价值
# dp[i][j]:可选物品是0-i，背包容量是j的时候能够装的最大价值
def knap(W,N,v,w):
    dp = [[0]*(W) for _ in range(N)]
    for j in range(W):
        dp[0][j] = v[0] if w[0]<=j else 0
    for i in range(1,N):
        for j in range(1,W):
            if w[i]>j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
    return dp[-1][-1]

N,W = map(int,input().split())
v,w = [],[]
for _ in range(N):
    weight,value = map(int,input().split())
    v.extend([value,value])
    w.extend([weight,weight])
print(knap(W,2*N,v,w))